﻿module main

type Counters =
    new() = { }

    static member g =
        Counters.qsC
    static member s =
        Counters.qsC <- ((+) Counters.qsC 1)

    [<DefaultValue>]
    static val mutable private qsC : int

let randomList (n : int) =
    let rnd = new System.Random()
    [ for i in {0 .. n} -> rnd.Next() ]

let rec putKey (k : 'T) (l : List<'T>) (r : List<'T>) (n : int) =
    match n with
    | 0 -> l @ [k] @ r
    | _ -> putKey (k) (l @ [r.Head]) (r.Tail) ((-) n 1)

let rec quickSort l =
    match l with
    | [] -> []
    | h::t -> quickSort (List.filter ((<) h) t) @ [h] @ (quickSort (List.filter ((>=) h) t))

let quickSortWithCounter l =
    Counters.s 
    quickSort l

let rec countSort l =
    let rec pairList (x : List<int>) (y : int) = 
        let nextMax = 
            if x <> [] then List.max [x.Head; y] else y
        match x with
        | [] -> []
        | h::t -> [[h; ((-) ((+) t.Length 1) (List.length (List.filter ((<>) h) t)))]] @ pairList (List.filter ((<>) h) t) nextMax
    pairList l 0

    //let (N : seq<int>) = Seq.initInfinite (fun x -> 0)
    //printfn "%A" (List.map (fun (x : int) -> ((+) (Seq.nth x N) 1)) l)

let rec conseqSearch needle haystack i =
    match haystack with
    | h::t when h = needle -> [i; i]
    | h::t when t = [] -> [-1; i]
    | _ -> conseqSearch needle haystack.Tail ((+) i 1)

let rec binarySearch needle (haystack : int[] ) low hi i =
    let midKey = (>>>) ((+) low hi) 1
    //printfn "!!!%A %A %A!!!" low hi midKey
    let midVal = haystack.[ midKey ]
    match midVal with
    | x when x < needle -> binarySearch needle haystack low midKey ((+) i 1)
    | x when x > needle -> binarySearch needle haystack midKey hi ((+) i 1)
    | x when x = needle -> (*[midKey, *)i//]
    | _ -> -1

let fillN (l : List<int>) n =
    let mutable aList = l
    while aList.Length < n do 
        aList <- aList @ [0]
    aList

let popN (l : List<int>) needle n =
    let mutable aList = l
    while aList.Length > n do 
        if aList.Head <> needle then aList <- aList.Tail
    aList

let LW1() =
    let seed = new System.Random()
    let needle = seed.Next()
    printfn "conseqSearch noNeedle,conseqSearch startNeedle,conseqSearch midNeedle,conseqSearch endNeedle,binSearch orderedArray"
    for i in [100;200;400;1000] do
        
        let theList = randomList i
        
        let noNeedle = fillN (List.filter ((<>) needle) theList) i
        
        let startNeedle = 
            popN 
                (
                putKey 
                    needle 
                    [] 
                    (List.filter ((<>) needle) theList) 
                    2
                ) 
                needle 
                i

        let midNeedle = 
            popN 
                (
                putKey 
                    needle 
                    [] 
                    (List.filter ((<>) needle) theList) 
                    ((>>>) i 1)
                ) 
                needle 
                i
        let endNeedle = 
            popN 
                (
                putKey 
                    needle 
                    [] 
                    (List.filter ((<>) needle) theList) 
                    (i - 2)
                ) 
                needle 
                i
        let sortedNeedle = quickSort startNeedle
        let unsortedLists = [noNeedle; startNeedle; midNeedle; endNeedle]
        List.iter (printf "%A,") 
            (List. map 
                (fun (x : List<int>) -> ((x.Tail).Head)) 
                    ((List.map (fun x -> conseqSearch needle x 1) unsortedLists))
            )
        printfn "%A" 
            (binarySearch needle (List.toArray sortedNeedle) 0 sortedNeedle.Length 1)
            

let LW2 =
    countSort [7;1;7;1;2;1;4;5;4]
    
let main (argv : string[]) =
    printfn "%A" LW2
    0
 //   printfn "%A" LW2
    //List.iter (printfn "%A") (quickSort (randomList 100))